import java.util.Arrays;

/**
* @description: 787. K 站中转内最便宜的航班
* @author hewei
* @date 2022/8/24 14:24
* @version 1.0
*/

public class FindCheapestPrice {

    int[][] g;
    int[][] dp;
    public int findCheapestPrice1(int n, int[][] flights, int src, int dst, int k) {
        if (src == dst) return 0;
        g = new int[n][n];
        dp = new int[n][k + 2];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        for (int i = 0; i < n; i++) {
            Arrays.fill(g[i], Integer.MAX_VALUE);
        }
        for (int[] flight : flights) {
            g[flight[0]][flight[1]] = flight[2];
        }
        int temp = process(src, dst, k + 1);
        return temp == Integer.MAX_VALUE ? -1 : temp;
    }

    public int process(int i, int target, int count) {
        if (i == target) {
            return 0;
        }
        if (count == 0) {
            dp[i][count] = Integer.MAX_VALUE;
            return Integer.MAX_VALUE;
        }
        if (dp[i][count] >= 0) return dp[i][count];
        int res = Integer.MAX_VALUE;
        for (int j = 0; j < g[i].length; j++) {
            if (g[i][j] != Integer.MAX_VALUE) {
                int temp = process(j, target, count - 1);
                if (temp != Integer.MAX_VALUE)
                res = Math.min(temp + g[i][j], res);
            }
        }
        dp[i][count] = res;
        return res;
    }

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        int[][] dp = new int[n][k + 2];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[src][0] = 0;
        for (int i = 1; i < k + 2; i++) {
            for (int[] flight : flights) {
                int a = flight[0], b = flight[1], c = flight[2];
                if (dp[a][i - 1] != Integer.MAX_VALUE) dp[b][i] = Math.min(dp[b][i], dp[a][i - 1] + c);
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < k + 2; i++) {
            ans = Math.min(ans, dp[dst][i]);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }
}